package toOffer;

import java.util.Objects;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/21 17:36
 * @description <p>寻找目标值</p>
 */
public class toOffer2_2_121NO {
    public static void main(String[] args) {
//        int[][] plants = {{5}};
        int[][] plants = {{2, 3, 6, 8}, {4, 5, 8, 9}, {5, 9, 10, 12}};
        int target = 5;
        System.out.println(findTargetIn2DPlants(plants, target));

    }

    /**
     * 2 3 6  8
     * 4 5 8  9
     * 5 9 10 12
     *
     * @param plants
     * @param target
     * @return
     */
    public static boolean findTargetIn2DPlants(int[][] plants, int target) {
        if (Objects.isNull(plants) || plants.length == 0 || plants[0].length == 0) {
            return false;
        }

        //先判断最低最高点与目标数的关系
        if (plants[plants.length - 1][plants[0].length - 1] < target) {
            return false;
        }
        if (plants[0][0] > target) {
            return false;
        }

        //以二维数组的左上角为坐标轴原点建立坐标系，初始化xy
        int y = plants.length - 1;
        int x = 0;
        while (x <= plants[0].length - 1 && y > 0) {
            if (plants[x][y] < target) {
                x++;
            }
            if (plants[x][y] > target) {
                y--;
            }
            if (plants[x][y] == target) {
                return true;
            }
        }
        return false;
    }
}
